package com.liufei.class03;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Code03_KM {

    public static int test(int[] arr, int k, int m) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                return num;
            }
        }
        return -1;
    }

    public static int getKTimeNum(int[] arr, int k, int m) {
        // 这里是O(1)的常数量，因为申请的空间是定长
        // t[0] 0位置的1出现的次数
        // t[1] 1位置的1出现的次数
        int[] t = new int[32];
        for (int num : arr) {
            for (int j = 0; j < 32; j++) {
//                if (((arr[i] >> i) & 1) != 0) {
//                    t[i]++;
//                }
                t[j] += ((num >> j) & 1);
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            // 说明这一位上有1
//            if (t[i] % m != 0) {
//                // 这里也可以使用 异或
//                ans |= (1 << i);
//            }

            if (t[i] % m == 0) {
                continue;
            }

            if (t[i] % m == k) {
                ans |= (1 << i);
            } else {
                return -1;
            }
        }

        // 这里需要额外处理0的情况
        if (ans == 0) {
            int count = 0;
            for (int num : arr) {
                if (num == 0) {
                    count++;
                }
            }
            if (count != k) {
                return -1;
            }
        }
        return ans;
    }


    public static int[] randomArr(int kinds, int range, int k, int m) {
        // 出现k次的num
        int kTimeNum = randomNumber(range);
        // 至少要有两种数
        int numKinds = (int) (Math.random() * kinds) + 2;
        // 0.5的概率是k，0.5的概率小于m就行
        int kTime = Math.random() < 0.5 ? k : (int) (Math.random() * (m - 1)) + 1;
        // 数组的长度
        int len = kTime + (numKinds - 1) * m;
        int[] arr = new int[len];
        // 现设置k的值
        int index = 0;
        for (; index < kTime; index++) {
            arr[index] = kTimeNum;
        }
        numKinds--;
        // 保证随机生成的数不重复
        Set<Integer> set = new HashSet<>();
        set.add(kTimeNum);
        // 然后设置m
        while (numKinds > 0) {
            int curNum = 0;
            do {
                curNum = randomNumber(range);
            } while (set.contains(curNum));
            set.add(curNum);
            numKinds--;
            for (int i = 0; i < m; i++) {
                arr[index++] = curNum;
            }
        }
        // 然后打乱数组种的顺序
        for (int i = 0; i < arr.length; i++) {
            // 随机生成一个下标，进行交换
            int j = (int) (Math.random() * arr.length);
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        return arr;
    }

    // [-range, range]
    public static int randomNumber(int range) {
        return ((int) (Math.random() * range) + 1) - (int) (Math.random() * range) + 1;
    }

    public static void main(String[] args) {
//        int[] arr = {1, 3, 3, 4, 1, 4, 3, 1};
//        int k = 2;
//        int m = 3;
//        int kTimeNum = getKTimeNum(arr, k, m);
//        System.out.println(kTimeNum);
        System.out.println("测试开始");
        int kinds = 10;
        int range = 200;
        int testTime = 10000;
        int max = 9;
        for (int i = 0; i < testTime; i++) {
            int a = (int) (Math.random() * max) + 1;  // [1, 9]
            int b = (int) (Math.random() * max) + 1;  // [1, 9]
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            // 保证 k < m
            if (k == m) {
                m++;
            }
            int[] arr = randomArr(kinds, range, k, m);
            int ans1 = getKTimeNum(arr, k, m);
            int ans2 = test(arr, k, m);
            if (ans1 != ans2) {
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束");
    }
}
